Samples of typical audio and video signals do not have a rectangular PDF (Probability Density Function) and for these data the efficiency advantage of entropy coding is well known. Quantisation followed by entropy coding allows commonly occurring small sample values to be encoded to a small number of bits, while infrequently occurring large sample values can take a larger number of bits. With correct design, the total number of bits in the coded signal is less than with straightforward binary or PCM (Pulse Code Modulation) coding of the quantised signal values.
Entropy coding however incurs some practical disadvantages. Firstly, the stream of coded data potentially has a variable data rate, which can be a considerable inconvenience for transmission over a fixed rate channel. Secondly, there is the likelihood of increased sensitivity to bit errors, because a single bit-error can propagate and thereby corrupt several samples.
The propagation of bit-errors arises because it is normal to pack the varying-length coded samples or codewords contiguously together. It is normal to code each sample using a prefix code, which has the property that a decoder can deduce from the initial segment of a codeword whether more bits follow or not. Once the start of the first codeword has been identified, a decoder can thus determine the end of that codeword. With contiguous packing, the next codeword follows immediately and an indefinite number of varying-length codewords can be correctly decoded. However, as single bit error may cause the end of a codeword to be incorrectly determined, and all subsequent codewords may be incorrectly decoded until the process is restarted at a known position within the stream.
Many schemes have been designed to ameliorate this problem. For example, the original signal may be divided into blocks each containing a constant number of samples, the output data format being similarly divided into blocks of constant size, each output block containing the entropy-coded data for one input block. Decoding then starts afresh for each block and an error can corrupt at most one block of data. The constant output block size must be chosen large enough to hold the largest amount of coded data from any input block, so there is wastage in the case of blocks that code to smaller amounts of data. Known improvements to and variations of simple block coding include allocating the coded data from each end of an output block, and incorporating pointers to intermediate positions within the block.
A very significant contribution to the field was “Error Resilient Entropy Coding” (EREC), as described in D. W. Redmill and N. G. Kingsbury, “The EREC: An error resilient technique for coding variable-length blocks of data”, IEEE Trans. on Image Processing, vol. 5, pp. 565-574, April 1996. EREC considers the output block as consisting of “slots” into which bits may be placed. In one embodiment of EREC, there is the same number of slots as there are codewords, and allocation of codewords to slots proceeds in a series of stages. At the first stage, there is one slot allocated to each codeword and the bits from the codeword are placed in its allocated slot if possible. In general some slots may not be completely filled after the first stage, and there may also be some slots whose allocated codewords are too large, so that some codeword bits must remain unplaced. In the second stage, a different allocation of slots to codewords is used, and for each codeword, an attempt is made to place remaining bits from the codeword into any vacant space in its newly-allocated slot. Further stages of allocation are then applied until all codeword bits have been placed.
An important feature of EREC is that the allocation of slots to codewords that is used at each stage is pre-determined: it does not depend on the lengths of the codewords. Therefore, bits that are placed in the first stage of the algorithm are in fixed locations: a decoder can look for these bits in the correct place regardless of any corruption of other bits during transmission. Bits that are placed in the second stage are slightly more vulnerable: the decoder may misjudge the starting position of those bits within their slot if there was an error in the bits that were placed in that slot during the first stage.
It will be clear that the error resilience given by EREC will be greatest for those bits that are placed at an early stage. The proportion of bits placed at an early stage can be increased by ensuring that the total capacity of the slots is significantly greater than the total number of bits in the codewords. However, to do so clearly results in wastage as there will be vacant space remaining in at least some of the slots at the end of the process.
If quantisation and coding are considered together, it is usually possible to adjust this total number of codeword bits by altering the quantisation resolution (step size or scale factor). However the optimal resolution, i.e. the resolution that results in codeword bits that exactly fill the output block, will generally not be known a priori, being dependent on the complexity of the information in the signal block. An initial trial encoding followed by adjustment of resolution is therefore required if the number of codeword bits is to be matched accurately to the size of an output block. Such an iterative approach is computationally expensive and may be impractical, in which case a margin must be allowed between the expected number of codeword bits and the size of the output block, generally resulting in wastage.
A further consideration is that a requirement to consider the data as consisting of blocks of significant size may be unduly restrictive. For example an audio signal has no natural block structure: coding such data as blocks necessarily incurs delay, which may be unacceptable in some critical applications. The EREC system as described in OD. W. Redmill and N. G. Kingsbury, “The EREC: An error resilient technique for coding variable-length blocks of data”, IEEE Trans. on Image Processing, vol. 5, pp. 565-574, April 1996 is adapted to the coding of video signals, and it takes advantage of the video block (or frame) structure. This system could therefore be considered unsuitable for use in audio applications in which delay is critical.
Hence there is a requirement for an efficient method of packing variable length signal data that is resilient to errors, that avoids wastage and that is configurable to situations in which delay must be minimised.